package com.ljy.my_study.leetcode.搜索二维矩阵;

import com.ljy.my_study.util.ArrayUtil;

/**
 * @author lijunying
 * @date 2021/9/18 10:57
 */
public class TestMain {

//    编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
//
//    每行中的整数从左到右按升序排列。
//    每行的第一个整数大于前一行的最后一个整数。
//             
//
//    示例 1：
//
//
//    输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
//    输出：true
//    示例 2：
//
//
//    输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
//    输出：false
//             
//
//    提示：
//
//    m == matrix.length
//    n == matrix[i].length
//1 <= m, n <= 100
//            -104 <= matrix[i][j], target <= 104
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/search-a-2d-matrix
//    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    public static void main(String[] args) {
        int[][] matrix= ArrayUtil.changeStr2Array("[[1,3,5,7],[10,11,16,20],[23,30,34,60]]");
        int target=4;
        System.out.println(new TestMain().searchMatrix(matrix,target));
    }

    public boolean searchMatrix(int[][] matrix, int target) {
        int m=matrix.length;
        int n=matrix[0].length;
        int len=m*n;
        int left=0;
        int right=len-1;
        if(target<getValue(matrix,left)||target>getValue(matrix,right)){
            return false;
        }
        while(left<right){
            int mid=(left+right)/2;
            int value=getValue(matrix,mid);
            if(target==value){
                return true;
            }
            if(target<value){
                right=mid;
            }else{
                left=mid+1;
            }
        }
        if(left<0||right>len){
            return false;
        }
        return target==getValue(matrix,right);
    }

    private int getValue(int[][] matrix,int index){
        int m=matrix.length;
        int n=matrix[0].length;
        int i=index/n;
        int j=index%n;
        return matrix[i][j];
    }
}
